This invention relates to a divider for dividing a natural number by a Mersenne number to provide a quotient and a remainder. This invention relates also to a parallel processor system for use in, among others, an electronic digital computer.
A Mersenne number, known in mathematics, is represented by (2.sup.n -1), where the exponent to two n represents a natural number. A Mersenne number becomes a Mersenne prime when the exponent n is equal to one of certain ones of the natural numbers. Examples of such natural numbers are 1, 2, 3, 5, 7, 13, 17, 19, 31, . . . , when the Mersenne numbers become 1, 3, 7, 31, 127, 8191, . . . . Inasmuch as the Mersenne number is herein used as a divisor for dividing a natural number, unity will be excluded from the Mersenne numbers and the Mersenne primes.
It is known to carry out division in an electronic digital computer by successive subtraction of a divisor from a dividend. The known process is time consuming particularly when the divisor is a prime number. When the dividend is given by g bits and the prime number, by r bits, the subtraction must be repeated (q-r) times with shift carries out a similar number of times. Because of the subtraction and shift repeated a number of times, the divider for a divisor equal to a prime number has a large volume of hardware. This is also the case with a divider for which a divisor is given by a Mersenne prime.
On the other hand, a parallel processor system comprising a plurality of processors and a plurality of memory modules is known, where a prime number is selected as the number of memory modules in order to suppress conflict of memory. An example of such a parallel processor system is described in a book "High Speed Computer and Algorithm Organization" edited by D. J. Kuck et al and published 1977 by Academic Press. According to Kuck et al, the prime number is rendered greater than the number of processors. The system described by Kuck et al is effective in carrying out numerical calculation according to algorithms of a certain type as, for example, in numerically solving differential equations. On accessing a memory cell of a desired one of the memory modules, each processor produces an address signal representative of a natural number. The natural number is divided by the prime number to provide a quotient and a remainder, by which the memory cell and the desired memory module are accessed, respectively. As pointed out hereinabove, it has heretofore been impossible to speedily carry out the division and extensive hardware has been indispensable. The parallel processor system has therefore been slow in operation and bulky when conflict of memory is suppressed. This applies even to the case where the prime number is selected from the Mersenne primes.